Multi-dimensional codes are widely used due to their potential efficiency. It is usually impractical to implement optimal decoding in the sense of maximal probability per information bit, such as maximum likelihood (ML) decoding, since the complexity may grow rapidly. To approximate the performance of ML decoding, it is proposed to perform a sub-optimal linear complexity decoding. The method is mainly suitable, but not limited, to concatenated multi-dimensional Bose-Chaudhuri-Hocquengham (BCH) codes.
FIG. 1A illustrates a prior art multi dimensional folded code that has p dimensions, wherein p is a positive integer. Each dimension may correspond a different ordering of the input data, and coded with BCH codes—each dimension is generated by applying a BCH code on data or on codewords of a previous dimension. The data to the codes may be folded over several columns or rows in order to obtain higher rate codes.
FIG. 1A illustrates a two dimensional folded code (p=2). In the example, a stream of data (also referred to as data) is divided into four parts, each part is encoded (using a BCH code) and a redundancy is appended to the end of that part. Each of these codewords (also referred as first codewords) are then folded into three columns which constitute (what we call) an outer code.
Matrix 100 of FIG. 1A includes thirteen columns 110(1)-110(13) and sixteen rows 120(1)-129(16). It stores four first codewords such as first codeword 130(1). Each first codeword includes thirty three data bits and three redundancy bits. First codeword 130(1) includes data bits 131(1) and redundancy bits 132(1). First codeword 130(2) includes data bits 131(2) and redundancy bits 132(2). First codeword 130(3) includes data bits 131(3) and redundancy bits 132(3). First codeword 130(4) includes data bits 131(4) and redundancy bits 132(4).
Each first codeword is stored in a folded manner in matrix 100. In other words matrix 100—stores folded version of each first codeword.
A second encoding process is appended on the first twelve bits of each two adjacent rows of matrix 100 to provide second codewords. The redundancy bits are stored in the thirteenth column 100(13) of matrix 100.
By grouping together the columns of the resultant outer code, a matrix is provided which is then divided into rows. Each one or more rows then constitute the data for another BCH encoding process to provide inner codewords. The redundancies of the inner code are grouped together and appended to the sequence of outer codewords.
It is noted that the inner codes and the outer codes may differ in that the redundancy of the outer code is also encoded by the inner code while the inner code's redundancy is not further encoded. Yet a further code may be appended to protect the redundancies of the inner codes.
The rate of the codes may be configured in several ways. For example, the length of the data/redundancy can differ from one code to another. The number of rows/columns for each code may be modified. Zero padding may be added to the matrix in order to complete the outer codes to full columns.
One important challenge during multi-dimensional decoding in hard/soft decoding is to identify false corrections (sometimes called miss-corrections)—these are situations where the decoder returns a valid correction of a codeword, which does not recover the original payload.